// 线性表的链式存储

#include "stdio.h"
#include "stdlib.h"

#define datatype int
typedef struct node
{
    datatype data;     //链表的数据域
    struct node *next; //链表的指针域
} LNode, *LinkList;

int Insert_LinkList(LinkList L, int i, datatype x);

//头插入法建立单链表算法
LinkList Creat_LinkList1()
{
    // 建立的时候元素个数
    int count, temp;
    // 头结点
    LNode *head;
    head = malloc(sizeof(LNode));
    head->next = NULL;
    printf("请输入元素个数:\n");
    scanf("%d", &count);
    printf("请按照元素个数依次输入元素值:\n");
    // 第一个有数据的结点
    LinkList node = malloc(sizeof(LNode));
    for (int i = 0; i < count; i++)
    {
        if (i == 0)
        {
            scanf("%d", &node->data);
            head->next = node;
        }
        else
        {
            scanf("%d", &temp);
            int c;
            node = head->next;
            LinkList tempNode = malloc(sizeof(LNode));
            tempNode->data = temp;
            tempNode->next = NULL;
            for (c = 0; c < i - 1; c++)
            {
                node = node->next;
            }
            node->next = tempNode;
        }
    }
    return head;
}

/*按序号查找 Get_Linklist(L,i)
在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/
LNode *Get_LinkList(LinkList head, int i)
{
    // 绝了 一回返回值用LinkList,一会不用
    LNode *res = head->next;
    if (i==1)
    {
        return res;
    }
    
    for (int c = 0; c < i-1; c++)
    {
       res = res->next;
    }
    return res;
}

/*插入运算 Insert_LinkList(L,i,x)
在单链表L的第i个位置上插入值为x的元素*/
int Insert_LinkList(LinkList head, int i, datatype x)
{
    int c;
    LinkList node = head->next;
    LinkList tempNode = malloc(sizeof(LNode));
    tempNode->data = x;
    tempNode->next = NULL;
    // 0的话是第一个的话比较特殊,要改变头结点的指向
    if (i==1)
    {
        head->next = tempNode;
        tempNode->next = node;
    }else{
        // 这里减2是因为 例如输入2的话就是在第一个有数据的结点后面插入
        // 此时只需要到这个第一个数据的结点就可以了
        for ( c = 0; c < i-2 ; c++)
        {
            node = node->next;
        }
        tempNode->next = node->next;
        node->next = tempNode;
    }
    
}

/*删除运算：Del_LinkList(L,i)
params i 要删除的元素的所在的下标
删除单链表L上的第i个数据结点*/
int Del_LinkList(LinkList head, int i)
{
    printf("要删除第%d个结点\n");
    // 同理,第一个的话要处理一下头结点
    LinkList node = head->next;
    LinkList temp = malloc(sizeof(LNode));
    if (i==1)
    {
        if (node->next == NULL)
        {
            // 就只有一个还要删除的话那就是吧head直接置为Null
            head = NULL;
            printf("唯一的结点已经删除\n");
            return 1;
        }
    }
    // 不然还是遍历到要删除的结点前前一个
    for (int z = 0; z < i-2; z++)
    {
        temp = node->next;
    }
    // 改变一下指向完事
    node->next = node->next->next;
    return 1;
}

void print(LinkList L) //输出单链表
{
    LNode *p = L->next;
    while (p->next != NULL)
    {
        printf("%d->", p->data); //输出表中非最后一个元素
        p = p->next;
    }
    printf("%d\n", p->data); //输出表中最后一个元素
}

int main()
{
    LinkList H;
    int i, j, k;
    datatype x;
    do
    {
        printf("\n\n\n\n");
        printf("\t\t\t 链表子系统\n");
        printf("\t\t*******************************\n");
        printf("\t\t*        1----建    表　  　　*\n");
        printf("\t\t*        2----插    入　　　　*\n");
        printf("\t\t*        3----删　　除　　　　*\n");
        printf("\t\t*        4----查　　找　　　　*\n");
        printf("\t\t*        5----显　　示　　　　*\n");
        printf("\t\t*        0----返　　回　　　　*\n");
        printf("\t\t*******************************\n");
        printf("\t\t 请选择菜单项(0－5)：");
        scanf("%d", &k);
        getchar();
        if (k == 1)
            H = Creat_LinkList1(); //用头插入法建立单链表
        else if (k == 2)           //在线性表第i位置处插入值为X的元素
        {
            printf("\n   请输入插入的位置i和数据X(输入格式：i,X):");
            scanf("%d,%d", &i, &x);
            j = Insert_LinkList(H, i, x);
        }
        else if (k == 3)
        {
            printf("\n   请输入要删除元素的位置i:");
            scanf("%d", &i);
            j = Del_LinkList(H, i);
            if (j == 1)
                printf("删除成功!!");
            else
                printf("删除失败!!");
        }
        else if (k == 4) //查找线性表中元素值为x的位置
        {
            printf("\n   请输入要查找的序号i:");
            scanf("%d", &i);
            LNode *p;
            p = Get_LinkList(H, i);
            if (p != NULL)
            {
                print(H);
                printf("线性表中序号为i的地址是 %d \n", p);
                printf("线性表中查找的序号%d的数据内容是%d\n",i,p->data);
            }
            else
                printf("链表中无此序号!!\n");
        }
        else if (k == 5) //输出链表
        {
            printf("\n表的存储顺序为：");
            print(H);
        }
    } while (k != 0);
    return 0;
}